package three;
import java.util.*;
public class A051 {

    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,-1,1};
        int m=grid.length,n=grid[0].length;
        boolean[][] check = new boolean[m][n];
        int key=0;//好橘子数量
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]==1) key++;
                else if(grid[i][j]==2) {
                    queue.add(new int[]{i,j});
                    check[i][j]=true;
                }
            }
        }
        int ret=0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            boolean hasRotten = false;
            for(int i=0;i<size;i++) {
                int[] t = queue.poll();
                for(int k=0;k<4;k++) {
                    int x = t[0]+dx[k];
                    int y = t[1]+dy[k];
                    //可以腐烂
                    if(x<m&&x>=0 &&y<n&&y>=0 && !check[x][y] && grid[x][y]==1) {
                        queue.add(new int[]{x,y});
                        check[x][y]=true;
                        hasRotten = true;
                        key--;
                    }
                }
            }
            if(hasRotten) ret++;
        }
        if(key==0) return ret;
        else return -1;
    }
}
